package DataStructure.arrayANDlist.list.listRealize;

import DataStructure.arrayANDlist.list.Listlj;
import DataStructure.arrayANDlist.list.Nodelj;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/1/6
 * @author—Email liujunfirst@outlook.com
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 输出链表的倒数第K个元素
 */

public class TheLastK {

    //method one
    public int getlastk(Listlj listlj1, int k) {
        SinglyLinkedList listlj = (SinglyLinkedList) listlj1;
        if (listlj == null || listlj.head.value == 0) {
            return Integer.MIN_VALUE;
        }
        Nodelj pre = listlj.head.next;
        Nodelj point = listlj.head.next;
        int count = 0;
        while (pre != null) {
            count++;
            pre = pre.next;
            if (pre != null && count >= k) {
                point = point.next;
            }
        }
        if (count >= k) {
            return point.value;
        }
        return Integer.MIN_VALUE;
    }

    //method two
    public int getlastk1(Listlj listlj1, int k) {
        SinglyLinkedList listlj = (SinglyLinkedList) listlj1;
        if (listlj == null || listlj.head.value == 0) {
            return Integer.MIN_VALUE;
        }
        Nodelj pre = listlj.head.next;
        Nodelj point = listlj.head.next;
        int count = 0;
        int newk = listlj.head.value - k;
        while (pre != null) {
            count++;
            pre = pre.next;
            if (count == newk) {
                point = pre;
            }
        }
        if (count < k) {
            return Integer.MIN_VALUE;
        }
        return point.value;
    }

    //method three
    public int getlastk_recursion(Listlj listlj1, int k) {
        SinglyLinkedList listlj = (SinglyLinkedList) listlj1;
        if (listlj == null || listlj.head.value == 0) {
            return Integer.MIN_VALUE;
        }
        int find = listlj.head.value - k + 1;
        recursion(listlj.head.next, find, 0);
        return target == null ? Integer.MIN_VALUE : target.value;
    }

    Nodelj target;

    private void recursion(Nodelj nodelj, int k, int count) {
        if (nodelj == null) {
            return;
        }
        recursion(nodelj.next, k, ++count);
        if (count == k) {
            target = nodelj;
            return;
        }
    }

}
